package floodfill;

public class Exercises2 {
    // 200、岛屿数量
    // 因为这个网格的四边都为水，那么我们只需要找网格内有多少个‘1’是相邻链接在一起的一个小网格的个数就可以了
    boolean[][] visit; // 记录 '1' 是否是走过
    int m;
    int n;

    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visit = new boolean[m][n];

        int ret = 0;
        // 进行寻找 '1' 开始的位置，只要找到了，并且visit对应的位置不为true。就把ret++，就相当于一个岛屿，之后进入dfs寻找与之相连的岛屿
        for(int i = 0;i < m;i++) {
            for(int j = 0;j < n;j++) {
                if(!visit[i][j] && grid[i][j] == '1') {
                    ret++;
                    dfs(grid,i,j);
                }
            }
        }
        return ret;
    }

    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};

    public void dfs(char[][] grid,int i,int j) {
        // 把进入dfs的位置对应的visit设置为true，因为只有grid[i][j] 为 '1' 才会进行
        visit[i][j] = true;
        for(int k = 0;k < 4;k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && grid[x][y] == '1') {
                dfs(grid,x,y);
            }
        }
    }
}
